'''
Created on Jul 15, 2009

@author: user
'''
import graph
import networkx.generators
import random
import cliques.utils
def createScaleFree(nodes,edges_per_node):
    new_graph = networkx.generators.barabasi_albert_graph(nodes, edges_per_node)
    return cliques.utils.networkx_to_pythongraph_no_weights(new_graph)    

def old_createScaleFree(nodes,edges):
    new_graph = graph.graph()
    new_graph.generate(nodes, 0)
    graph_nodes = new_graph.nodes()
    connected_component = set([graph_nodes[0]])
    for node in graph_nodes[1:]:
        neighbor = choose_neighbor(connected_component,new_graph,node)
        new_graph.add_edge(node, neighbor)
        connected_component.add(node)
        #print "Added %s-%s" % (node,neighbor)
        edges=edges-1
        
    while edges>0:
        random_node_index = random.randint(0,nodes-1)
        random_node = graph_nodes[random_node_index]
        possible_neighbors = set(graph_nodes)
        possible_neighbors.remove(random_node)
        possible_neighbors.difference_update(new_graph.neighbors(random_node))
        if len(possible_neighbors)>0:
            neighbor = choose_neighbor(possible_neighbors,new_graph,random_node)
            new_graph.add_edge(random_node, neighbor)
            #print "Added %s-%s" % (random_node,neighbor)        
            edges=edges-1
    return new_graph

def choose_neighbor(possible_neighbors,new_graph, node):
    ''' Choose node randomly, prioritizing nodes with high degrees '''
    if len(possible_neighbors)==1:
        return possible_neighbors.__iter__().next()
    
    value_to_node = list()
    sum_degree = 0
    for neighbor in possible_neighbors:
        degree=new_graph.order(neighbor)
        values = list(xrange(degree))
        for i in xrange(degree):
            values[i]=neighbor
        value_to_node.extend(values)
        sum_degree=sum_degree+degree
    random_value = random.randint(0,max(0,sum_degree-1))
    return value_to_node[random_value]




    